package formal.linkedList;

/**
 * 两两交换链表中的节点
 *
 * @author DengYuan2
 * @create 2021-01-07 21:13
 */
public class M_24 {
    public static void main(String[] args) {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(4);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        ListNode listNode = swapPairs2(n1);
        System.out.println(listNode);
    }

    /**
     * 我的写法：递归
     *
     * @param head
     * @return
     */
    public static ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode first = head;
        ListNode second = head.next;
        first.next = swapPairs(second.next);
        second.next = first;
        return second;
    }

    /**
     * 官方-迭代
     * @param head
     * @return
     */
    public static ListNode swapPairs2(ListNode head) {
        ListNode listNode = new ListNode(-1);
        listNode.next = head;
        ListNode tmp = listNode;
        while (tmp.next != null && tmp.next.next != null) {
            ListNode first =tmp.next;
            ListNode second = tmp.next.next;

            first.next=second.next;
            second.next=first;
            tmp.next=second;
            tmp =first;
        }
        return listNode.next;


    }
}
